The present invention relates to a Viterbi decoding method and a Viterbi decoding apparatus in which the Viterbi algorithm being an example of a most likelihood decoding method of convolutional codes is used as an error correction method at the digital transmission. The Viterbi algorithm is described, for example, in Proceeding of IEEE, vol. 61, pp. 268-278, Mar. 1973, by G. D. Forney Jr.
As a system of a digital transmission, there is a packet communication system in which data to be transmitted is divided into packets of a certain bit length (word length) and which transmits the data in a packet unit. At the packet communication system, at the time when two packets transmitted in sequence are received at a receiving side, the time interval between packets is generally not fixed. In the space communication and the mobile communication for such as a mobile phone, a Viterbi decoding apparatus has been used for the error correction. FIG. 1 is a block diagram showing a conventional Viterbi decoding apparatus. Referring to FIG. 1, the operation of the conventional Viterbi decoding apparatus used in a packet communication system is explained. In this, it is defined that the receiving soft decision P data and Q data are three bits respectively.
The conventional Viterbi decoding apparatus 59 shown in FIG. 1 provides input terminals 41 and 42 to which the receiving soft decision P data and Q data are inputted respectively, a selector 3 which switches the group of the receiving soft decision P data and Q data, and the group of xe2x80x9c000xe2x80x9d data, a branch metric generator 4 which obtains the metric of the output of the selector 3 by comparing the output of the selector 3 with each transmitting data of a group of transmitting data, a path metric register 6 which stores the accumulated metric of survivor path, an ACS (add, compare and select) circuit 5 which outputs a path metric value of xe2x80x9cnxe2x80x9d state (n is an integer of two or more) and selecting information (branch value) of xe2x80x9cnxe2x80x9d state every symbol interval based on the outputs of the branch metric generator 4 and the path metric register 6, a path memory 7 which stores the selecting information of xe2x80x9cnxe2x80x9d state outputted from the ACS circuit 5 every symbol interval, a most likelihood path state detector 9 which obtains a state number having a maximum path metric from the path metric values of xe2x80x9cnxe2x80x9d state outputted from the ACS circuit 5 every symbol interval, a trace back circuit 48 which performs a trace back process for the data in the path memory 7 and outputs the obtained result as a decoded data from an output terminal 16, and a control circuit 50 which controls this whole Viterbi decoding apparatus 59. The xe2x80x9c000xe2x80x9d data inputting to the selector 3 are, after the last part of the packet data are inputted, during the packet data are decoded, the data (terminal data) which makes each circuit in the Viterbi decoding apparatus 59 return to the state before the packet data are inputted. In this, three bit soft decision data are inputted to the Viterbi decoding apparatus 59, therefore the xe2x80x9c000xe2x80x9d data are composed of three bit binary figure xe2x80x9c0xe2x80x9d.
The ACS circuit 5 outputs the compared and selected path metric value of xe2x80x9cnxe2x80x9d state and selecting information of xe2x80x9cnxe2x80x9d state, by adding, comparing and selecting the outputs of the branch metric generator 4 and the path metric register 6, every symbol interval, corresponding to a trellis line diagram. The trace back circuit 48 outputs a path memory control signal to the path memory 7 and reads data from the path memory 7, with this, every xe2x80x9cgxe2x88x92fxe2x80x9d symbols, traces back the path memory 7 to the past only for xe2x80x9cgxe2x80x9d symbol from the state number of the output of the most likelihood path state detector 9 and outputs xe2x80x9cgxe2x88x92fxe2x80x9d bits from the finally reached bits as decoded data.
The Viterbi decoding apparatus 59 further provides a receiving clock input terminal 52 to which a receiving clock is inputted and supplied to the branch metric generator 4, the ACS circuit 5, the path metric register 6, the path memory 7 and the trace back circuit 48, an input terminal 54 which a packet data starting pulse is inputted to and supplies the pulse to the control circuit 50 and an input terminal 55 which a packet data finishing pulse is inputted to and supplies the pulse to the control circuit 50. The control circuit 50 outputs a select signal to the selector 3, and outputs a path metric set signal to the path metric register 6 and outputs a trace back starting signal to the trace back circuit 48. Moreover, the control circuit 50 gives a high path metric to the state number xe2x80x9c0xe2x80x9d of the path metric register 6 and gives the same low path metric, for example xe2x80x9c0xe2x80x9d, to the other state numbers by the packet data starting pulse and makes the Viterbi decoding operate. After the packet data finishing pulse is inputted, the control circuit 50 switches the output of the selector 3 to the data group xe2x80x9c000xe2x80x9d, during the Viterbi decoding is operated and at the time when the output of the most likelihood path state detector 9 becomes the state number xe2x80x9c0xe2x80x9d, the control circuit 50 makes the operation of the branch metric generator 4, the ACS circuit 5, the path metric register 6 and the most likelihood path state detector 9 stop and makes the trace back circuit 48 perform the trace back from the series connecting to the most likelihood path of the state number xe2x80x9c0xe2x80x9d.
Next, the operation of the conventional Viterbi decoding apparatus 59 for the packet data processing is explained. In this, in order to make the explanation understandable, the case that a coding ratio R=1/2 and a constraint length K=3 is explained.
First, a coding apparatus of transmission side using with this Viterbi decoding apparatus is explained. FIG. 2 is a block diagram showing a convolutional coding apparatus. At the transmission side, as shown in FIG. 2, the convolutional coding apparatus 23 is constituted of a three stage shift register 20 and Exclusive-OR gates 21 and 22. And inputted data are coded by this convolutional coding apparatus 23. The series of data is inputted to the shift register 20 from an input terminal 24 every symbol interval. And the output of each stage designated by the shift register 20 is logically operated by the Exclusive-OR gates 21 and 22, and P data and Q data are outputted from output terminals 25 and 26 respectively. The shift register 20 is made to reset by giving a reset signal.
FIG. 3 is a series of data diagram showing a series of transmitted data and a series of convolutionally coded data. As shown in FIG. 3, at the case that the xe2x80x9cdxe2x80x9d pieces of the packet data i1, i2, . . . , id are convolutionally coded, generally the convolutional coding apparatus 23 is made to reset before the data i1 is inputted. That is, the contents of each stage of the shift register 20 are made to be xe2x80x9c0xe2x80x9d. And after the last packet data id is inputted to the shift register 20, the xe2x80x9cthe constraint length Kxe2x88x921xe2x80x9d pieces of xe2x80x9c0xe2x80x9d is inputted. In this, the constraint length K=3, therefore two pieces of xe2x80x9c0xe2x80x9d data are inputted. In FIG. 3, the P data and Q data outputted from the convolutional coding apparatus 23 are denoted as P1, P2, . . . , Pd, Pd+1, Pd+2 and Q1, Q2, . . . , Qd, Qd+1) Qd+2 respectively.
The P data and Q data being the output of the convolutional coding apparatus 23 are transmitted and inputted to the Viterbi decoding apparatus 59 in FIG. 1. At this time, in order for the Viterbi decoding apparatus 59 to make use of the additional information of the P data and Q data corrupted by noise over the channel, the received P data and Q data are expressed in the soft decision. FIG. 4 is soft decision data diagram showing three bit soft decision data for xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d data. In FIG. 4, the above mentioned soft decision data are shown.
Next, the operation of the conventional Viterbi decoding apparatus 59 shown in FIG. 1 is explained. FIG. 5 is a trellis diagram showing the trellis expression of the convolutional coding apparatus 23 shown in FIG. 2. In FIG. 5, {0,0}, {0,1},{1,0} and {1,1} show {a,b}, that is, the contents of the first and second stages of the shift register 20 in the convolutional coding apparatus 23 are shown. In this, xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d are variables expressing the contents of each one bit of the first and second stages of the shift register 20 respectively. The values positioned at the sides of arrow marks placed at the right sides of the {0,0}, {0,1}, {1,0} and {1,1} are the calculated values (axc3x972+b), and these values are called as state numbers.
The trellis diagram shown in FIG. 5 is briefly explained. At the case that the state number is xe2x80x9c0xe2x80x9d and the data inputting next to the convolutional coding apparatus 23 is xe2x80x9c0xe2x80x9d, the state number is shifted to xe2x80x9c0xe2x80x9d and xe2x80x9c0 0xe2x80x9d is outputted as the output value of the P data and the Q data. And at the case that the state number is xe2x80x9c0xe2x80x9d and the data inputting next to the convolutional coding apparatus 23 is xe2x80x9c1xe2x80x9d, the state number is shifted to xe2x80x9c1xe2x80x9d, and xe2x80x9c1 1xe2x80x9dis outputted as the output value of the P data and the Q data. At the case that the state numbers are the other numbers, the shifting destination is determined corresponding to the inputting data to the convolutional coding apparatus 23. The outputting values of the P data and Q data at those times are described at above the line showing the shift. The Viterbi decoding apparatus 59 performs the decoding process corresponding to this trellis diagram.
At the Viterbi decoding apparatus 59, after the packet data starting pulse is inputted to the control circuit 50, the control circuit 50 outputs a path metric set signal to the path metric register 6. The path metric register 6 gives a high metric (for example, 64) to the register of the state number xe2x80x9c0xe2x80x9d, and gives metric xe2x80x9c0xe2x80x9d to the register of the state numbers xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d and xe2x80x9c3xe2x80x9d. At this time, the control circuit 50 sets a select signal for the selector 3, in order that the selector 3 selects the group of the receiving soft decision P data and Q data and outputs them.
First, after the soft decision data for P1 and Q1 are inputted to the branch metric generator 4 through the selector 3 from the input terminals 41 and 42, the branch metric generator 4 calculates the metric for soft decision P1 data and Q1 data, that is, calculates the branch metric associated with all the branches (0, 0), (1, 0), (0, 1) and (1, 1). For the soft decision P1 data and Q1 data, the branch metric at the time when the branch is (0, 0) is defined as xcex0, the branch metric at the time when the branch is (1, 0) is defined as xcex1, the branch metric at the time when the branch is (0, 1) is defined as xcex2, and the branch metric at the time when the branch is (1, 1) is defined as xcex3. The branch metric generator 4 outputs these xcex0, xcex1, xcex2 and xcex3 to the ACS circuit 5. FIG. 6 is a diagram showing an explanation of the ACS circuit. As shown in FIG. 6, at this time, path metric values of each state number 0, 1, 2 and 3 at time m0 are defined as xcex930(m0), xcex931(m0), xcex932(m0) and xcex933(m0) respectively. Actually, the time is soon after the metric set has been done, therefore each path metric value is xcex930(m0)=64, xcex931(m0)=0. xcex932(m0)=0 and xcex933(m0)=0.
The path metric register 6 outputs these xcex930(m0), xcex931(m0), xcex932(m0) and xcex933(m0) to the ACS circuit 5 and the ACS circuit 5 performs the operation based on the trellis shown in FIG. 6.
Next, this operation is explained. At time m1, the shifts merged into the state number xe2x80x9c0xe2x80x9d are ones from the state number xe2x80x9c0xe2x80x9d and xe2x80x9c2xe2x80x9d. The output data from the convolutional coding apparatus 23 at the shift from the state number xe2x80x9c0xe2x80x9d is xe2x80x9c0 0xe2x80x9d, therefore the branch metric becomes xcex0, and the output data from the convolutional coding apparatus 23 at the shift from the state number xe2x80x9c2xe2x80x9d is xe2x80x9c1 1xe2x80x9d, therefore the branch metric becomes xcex3, and the path metric values of the state number xe2x80x9c0xe2x80x9d and xe2x80x9c2xe2x80x9d at time m0 are xcex930(m0) and xcex932(m0) respectively. Therefore, the operation of xcex930(m0)+xcex0 and xcex932(m0)+xcex3 are performed respectively and larger value within these operation is made to be the path metric value xcex930(m1) at time m1 and at the state number xe2x80x9c0xe2x80x9d, and is stored into the path metric register 6. At the same time, the selected branch value (in FIG. 6, at the case that the value shown as the continuous line is selected, the value is xe2x80x9c0xe2x80x9d, and the value shown as the broken line is selected, the value is xe2x80x9c1xe2x80x9d) is stored as a selected value S0(m1) of the state number xe2x80x9c0xe2x80x9d at time m1 in the path memory 7. Following this, path metric values xcex931(m1), xcex932(m1), xcex933(m1) and branch values S1(m1), S2(m1), S3(m1) at time m1 are calculated and are stored into the path metric register 6 and the path memory 7 respectively. In this, it is defined that the path memory 7 has a memory capacity which can store the branch information for xe2x80x9cg+fxe2x80x9d symbols. The ACS circuit 5 outputs the path metric values xcex930(m1), xcex93(m1), xcex932(m1) and xcex933(m1) calculated at time m1 to the path metric register 6, at the same time also outputs them to the most likelihood path state detector 9. With the mentioned above operation, a series of process at time m1 is finished. Hereinafter this series of process is referred to as an ACS process.
At the time when next soft decision P2 data and Q2 data are inputted, the mentioned above ACS process is repeatedly performed. After finishing the process at time mg, the control circuit 50 gives an instruction that a trace back process mentioning later is performed to the trace back circuit 48 and the most likelihood path state detector 9. The most likelihood path state detector 9 outputs the state number having the maximum path metric value from the most likelihood path metric values xcex930(mg), xcex931(mg), xcex932(mg) and xcex933(mg) to the trace back circuit 48. FIG. 7 is a trellis diagram showing a trace back process. At the case that the state number having the maximum path metric value at time mg is xe2x80x9c2xe2x80x9d, the trace back circuit 48 reads the contents of the path memory 7 and traces back the path connecting to the state number xe2x80x9c2xe2x80x9dhaving the maximum path metric value at time mg expressing a continuous line shown in FIG. 7. The trace back circuit 48 examines that the path merging into the state number xe2x80x9c2xe2x80x9d is whether the state number xe2x80x9c1xe2x80x9d or xe2x80x9c3xe2x80x9d by reading out the data stored in the state number xe2x80x9c2xe2x80x9d at time mg from the path memory 7, and knows it from the state number xe2x80x9c1xe2x80x9d. This process is traced back to time m0 by the repetition of the same operation. Finally, the trace back circuit 48 outputs the xe2x80x9cgxe2x88x92fxe2x80x9d pieces of data (data from time m1 to time mgxe2x88x92f) from the data read from the path memory 7 as decoded data, from the output terminal 16. Hereinafter this process is referred to as a trace back process. At the time when the trace back process is performed by synchronizing with the receiving clock, the ACS process is performed by synchronizing with the receiving clock. It is defined that the path memory 7 can perform the writing process at the time of the ACS process and the reading process at the time of the trace back process at the same time. FIG. 8 is a diagram showing the structure of a ring memory. As shown in FIG. 8, the path memory 7 is formed as ring structure and has a memory capacity for xe2x80x9cg+fxe2x80x9d symbols, therefore the over writing to the necessary data by the ACS process can be avoided. After this, at the time when the ACS process for xe2x80x9cgxe2x88x92fxe2x80x9d symbols is performed, the trace back process is performed and the decoded data are outputted.
After the last soft decision Pd+2 data and Qd+2 data are inputted from the input terminals 41 and 42 and the ACS process is finished, a packet data finishing pulse is inputted to the control circuit 50. By the input of this pulse, the control circuit 50 sets a select signal for the selector 3 in order that the group of xe2x80x9c000xe2x80x9d data (terminal data) is outputted from the selector 3. After this, the group of xe2x80x9c000xe2x80x9d data of at least for xe2x80x9cg+fxe2x80x9d symbols must be continuously inputted, synchronizing with the receiving clock. During this, in order to obtain the last data id of the packet, the mentioned above ACS process and trace back process are repeatedly performed. In the mentioned above explanation, the process at the group of xe2x80x9c000xe2x80x9d data is explained, this comes from that the three bit data are used as the receiving soft decision data. At the case that the two bit data are used as the receiving soft decision data, the group of xe2x80x9c00xe2x80x9d data must be continuously inputted at least for xe2x80x9cg+fxe2x80x9d symbols.
Regarding that the group of xe2x80x9c000xe2x80x9d data must be continuously inputted, for example, this is described in the data book of Viterbi decoding apparatus LSI, model name Q 1900, made by Qualcom Inc. In this data book, there is a description that after the decoding of the packet data is finished, the 103 pieces of xe2x80x9c000xe2x80x9d data must be inputted.
At the mentioned above conventional Viterbi decoding apparatus, at the time when the decoding of the packet data is processed, after finishing the decoding of the packet data, the xe2x80x9c000xe2x80x9d data for xe2x80x9cg+fxe2x80x9d symbols must be absolutely inputted. Therefore, next packet data to be inputted are made to wait for xe2x80x9cg+fxe2x80x9d symbols and there is a problem that the packet transmission efficiency is deteriorated. And at the case that next packet data are inputted before waiting for xe2x80x9cg+fxe2x80x9d symbols, there is a problem that the last part of the existing packet data is not decoded correctly.
It is therefore an object of the present invention to provide a Viterbi decoding method and a Viterbi decoding apparatus, even though at the case that next packet data are continuously inputted after the existing packet data to the Viterbi decoding apparatus, which can decode the last part of the existing packet data correctly.
For achieving the above mentioned objects, at a Viterbi decoding method, which receiving data are inputted to, generates a branch metric from said receiving data, performs a ACS (add, compare and select) process for said branch metric, generates path metric values being plural states and selecting information, stores said selecting information, decides the most likelihood path based on the maximum path metric value, and traces back said stored selecting information based on said decided most likelihood path, and outputs decoded data, said receiving data are packet data. And a Viterbi decoding method includes a process, during said packet data are received, which performs generating said branch metric, said ACS process, deciding said most likelihood path and outputting said decoded data, based on a first operating clock synchronized with said packet data, and a process, at the time when the reception of said packet data is finished, which switches to a second operating clock being faster than said first operating clock, performs generating said branch metric and said ACS process and deciding said most likelihood path, based on said second operating clock.
A first Viterbi decoding apparatus of the present invention provides, a first selector which switches receiving data and terminal data and outputs the selected data, a branch metric generator which the output of said first selector is inputted to and obtains the metric of said inputted data, a path metric register which stores the accumulated metric of the survivor path, an ACS circuit which performs an ACS process based on the output of said branch metric generator and the output of said path metric register every symbol interval and outputs path metric values of plural states and selecting information, a most likelihood path state detector which detects a most likelihood path having the maximum path metric value from said path metric values of plural states, a path memory which stores the selecting information of said plural states every symbol interval, and a trace back circuit which traces back to the past said path memory for only xe2x80x9cgxe2x80x9d symbol every xe2x80x9cgxe2x88x92fxe2x80x9d symbols based on said most likelihood path and outputs xe2x80x9cgxe2x88x92fxe2x80x9d bits from finally reached bits as decoded data, and said receiving data are packet data. And a Viterbi decoding apparatus, selects said packet data by said first selector during said packet data are received and also drives said branch metric generator, said ACS circuit, said path metric register, said path memory and said trace back circuit by a first operating clock synchronized with said packet data, makes said first selector switch to said terminal data side at the time when the reception of said packet data is finished, and drives said branch metric generator, said ACS circuit, said path metric register and said path memory by a second operating clock being faster than said first operating clock after the reception of said packet data is finished.
A second Viterbi decoding apparatus of the present invention, which provides a selector which switches receiving data and terminal data and outputs the selected data, a branch metric generator which the output of said selector is inputted to and obtains the metric of said inputted data, a path metric register which stores the accumulated metric of the survivor path, an ACS circuit which performs an ACS process based on the output of said branch metric generator and the output of said path metric register every symbol interval and outputs path metric values of plural states and selecting information, a most likelihood path state detector which detects a most likelihood path having the maximum path metric value from said path metric values of plural states, a path memory which stores the selecting information of said plural states every symbol interval, and a trace back circuit which traces back to the past said path memory for only xe2x80x9cgxe2x80x9d symbol every xe2x80x9cgxe2x88x92fxe2x80x9d symbols based on said most likelihood path and outputs xe2x80x9cgxe2x88x92fxe2x80x9d bits from finally reached bits as decoded data and said receiving data are packet data. And a Viterbi decoding apparatus, selects said packet data by said selector during said packet data are received and also makes said selector switch to said terminal data side corresponding to that the reception of said packet data is finished and makes said branch metric generator set the branch metric corresponding to said terminal data, wherein said path memory is a ring memory which stores said selecting information of xe2x80x9c2f+gxe2x80x9d symbols.
A Viterbi decoding apparatus of the present invention processes the last part of the packet data smoothly and correctly, and even next packet data are inputted soon after the existing packet data, the last part of the existing packet data can be decoded correctly. In order to achieve this, at the time when the input of the packet data is finished, the operating clock of the Viterbi decoding apparatus is made to be fast and the process time for the terminal data is made to be reduced. Instead of making the operating clock fast, making the memory capacity of the path memory composed of a ring memory large and with this, the branch metric for the terminal data is known beforehand, therefore it is possible that the branch metric generator sets the branch metric beforehand.